#include <limits.h>  // INT_MIN,INT_MAX
#include <math.h>    // abs,pow

#include <algorithm>      // sort
#include <iostream>       // cout,cin
#include <numeric>        // accumulate
#include <string>         // string
#include <unordered_map>  // unordered_map
#include <unordered_set>  // unordered_set
#include <vector>         // vector

using namespace std;

// 如果x是2的幂则返回True，否则返回False
bool IsPowerOf2(int x) { return (x & (x - 1)) == 0; }

class Solution {
   public:
    string minWindow(string s, string t) {
        int size1 = s.size(), size2 = t.size();

        // 统计t中字符出现次数
        unordered_map<char, int> count;
        for (int i = 0; i < size2; i++) {
            count[t[i]]++;
        }

        int l = 0, r = 0;  // 滑动窗口左右边界
        int need = size2;  // 当前需要的字符数

        int ans_len = size1 + 1;
        int ans_idx = l;

        while (r < size1) {
            // 寻找满足条件的右侧边界
            while (r < size1 && need > 0) {
                count[s[r]]--;
                if (count[s[r]] >= 0) {
                    need--;
                }
                r++;
            }

            // 调整左侧边界
            while (l < r) {
                if (count[s[l]] < 0) {
                    count[s[l]]++;
                    l++;
                } else {
                    break;
                }
            }

            if (need == 0 && r - l < ans_len) {
                ans_len = r - l;
                ans_idx = l;
            }

            // 滑动窗口左侧边界
            count[s[l]]++;
            need++;
            l++;
        }

        if (ans_len == size1 + 1) {
            return "";
        } else {
            return s.substr(ans_idx, ans_len);
        }
    }
};

int main() {
    Solution solution;
    return 0;
}